Section: New Results

Efficient Filtering Algorithms and Heuristics for Dedicated Constraints (filtering)

Participants : Jean-Guillaume Fages, Xavier Lorca, Arnaud Malapert, Narendra Jussien.

1. Revisiting the tree constraint We revisit the tree constraint introduced at CPAIOR 2005 in  [35] which partitions the nodes of a n-nodes, m-arcs directed graph into a set of node-disjoint anti-arborescences for which only certain nodes can be tree roots. We introduce in a new filtering algorithm that enforces generalized arc-consistency in O(n+m) time while the original filtering algorithm reaches O(nm) time. This result allows to tackle larger scale problems involving graph partitioning in CHOCO .

   The corresponding paper Revisiting the tree Constraint was published at the 17th International Conference on Principles and Practice of Constraint Programming (CP 2011 ), [18] .

2. An Optimal Constraint Programming Approach to the Open-Shop Problem We present an optimal constraint programming approach for the Open-Shop problem, which integrates recent constraint propagation and branching techniques with new upper bound heuristics for the Open-Shop problem. Randomized restart policies combined with nogood recording allow to search diversification and learning from restarts. This approach closed all remaining problems of the Brucker et al. and Guéret and Prins benchmarks with cpu times that are orders of magnitude lower than the best known metaheuristics.

   The corresponding paper An Optimal Constraint Programming Approach to the Open-Shop Problem was published in the INFORMS Journal on Computing  [13] . This work was done in collaboration with H. Cambazard (4C , INP Grenoble ), C. Guéret (IRCCyN ), A. Langevin (Ecole Polytechnique Montréal ) and L.-M. Rousseau (Ecole Polytechnique Montréal ).